#include "xp.h"

#include "assert.h"

#include <string.h>
#include <ctype.h>

#define T XP_T

// For base:1 << 8
// 2147483647: unsigned char x[] = {255, 255, 255, 127}
// 256: unsigned char x[] = {0, 1}
#define BASE (1 << 8)

// Returns the number of significant digits, not counting the leading zeros.
int XP_length(int n, T x)
{
    while (n > 1 && x[n - 1] == 0)
        n--;
    return n;
}

unsigned long XP_fromint(int n, T z, unsigned long u)
{
    int i = 0;
    do {
        z[i++] = u % BASE;
    } while ((u /= BASE) > 0 && i < n);
    for (; i < n; i++)
        z[i] = 0;
    return u;
}

unsigned long XP_toint(int n, T x)
{
    unsigned long u = 0;
    int i = (int)sizeof(u);
    if (i > n)
        i = n;
    while (--i >= 0)
        u = u*BASE + x[i];
    return u;
}

int XP_cmp(int n, T x, T y)
{
    int i = n-1;
    while (i > 0 && x[i] == y[i])
        i--;
    return x[i] - y[i];
}

// carry: 0 or 1
int XP_add(int n, T z, T x, T y, int carry)
{
    for (int i = 0; i < n; i++) {
        // The max value for single digit: BASE-1 + BASE-1 + 1 = 2*BASE - 1.
        // So can store in a int.
        carry += x[i] + y[i];
        z[i] = carry % BASE;
        carry /= BASE;
    }
    return carry; // MSB carry
}

// borrow: 0 or 1
int XP_sub(int n, T z, T x, T y, int borrow)
{
    for (int i = 0; i < n; i++) {
        // The max value for single digit: BASE-1 + BASE - 0 - 0 = 2*BASE - 1.
        // So can store in a int.
        int d = (x[i]+BASE) - borrow - y[i];
        z[i] = d % BASE;
        borrow = 1 - d/BASE;
    }
    return borrow; // MSB borrow
}

// y: [0, BASE-1]
int XP_sum(int n, T z, T x, int y)
{
    for (int i = 0; i < n; i++) {
        y += x[i];
        z[i] = y % BASE;
        y /= BASE;
    }
    return y; // MSB carry
}

// y: [0, BASE-1]
int XP_diff(int n, T z, T x, int y)
{
    for (int i = 0; i < n; i++) {
        int d = (x[i]+BASE) - y;
        z[i] = d % BASE;
        y = 1 - d/BASE;
    }
    return y; // MSB borrow
}

// carry: 0: one's complement negation 1: two's complement negation
int XP_neg(int n, T z, T x, int carry)
{
    for (int i= 0; i < n; i++) {
        carry += (unsigned char)~x[i];
        z[i] = carry % BASE;
        carry /= BASE;
    }
    return carry;
}

// Assert the length of z is m+n
int XP_mul(T z, int n, T x, int m, T y)
{
    unsigned int carry = 0;
    int carryout = 0;
    for (int i = 0; i < n; i++) {
        int j;
        for (j = 0; j < m; j++) {
            // The max value for single digit: (BASE-1) * (BASE-1) + (BASE-1) = BASE*BASE - BASE
            // So can store in a unsigned int
            carry += x[i] * y[j] + z[i + j];
            z[i + j] = carry % BASE;
            carry /= BASE;
        }
        for (; i+j < m+n; j++) {
            carry += z[i + j];
            z[i + j] = carry % BASE;
            carry /= BASE;
        }
        carryout |= carry;
    }
    return carryout;
}

// y: [0, BASE-1]
int XP_product(int n, T z, T x, int y)
{
    unsigned int carry = 0;
    for (int i = 0; i < n; i++) {
        carry += x[i] * y;
        z[i] = carry % BASE;
        carry /= BASE;
    }
    return carry;
}

// assert the length of tmp: n+1 + m+1
int XP_div(int n, T q, T x, int m, T y, T r, T tmp)
{
    int nx = n, my = m;
    n = XP_length(n, x);
    m = XP_length(m, y);
    if (m == 1) {
        // single-digit division
        if (y[0] == 0)
            return 0;
        r[0] = XP_quotient(n, q, x, y[0]);
        memset(r+1, '\0', my-1);

    } else if (m > n) {
        memset(q, '\0', nx);
        memcpy(r, x, n);
        memset(r+n, '\0', my-n);

    } else {
        // long division
        // rem: n+1 dq: m+1
        unsigned char *rem = tmp, *dq = tmp + n+1;
        assert(m >= 2 && m <= n);

        memcpy(rem, x, n);
        // 小技巧：被除数最高位之前补一个 0 数位，使得 n 大于 ,
        // 每次 m+1 位被除数除以除数，产生 m+1 位余数，实际余数 m 位 .
        rem[n] = '\0';

        int k;
        for (k = n-m; k >= 0; k--) {
            // Compute qk
            // 用 rem 的前三个位数除以 y 的前两个位数，即可得到对 qk 的估计值，该值可能是正确的或比正确值 1
            int qk;
            int km = k + m;
            unsigned long y2 = y[m-1]*BASE + y[m-2];
            unsigned long r3 = rem[km] * BASE*BASE + rem[km-1] * BASE + rem[km-2];
            qk = r3 / y2;
            if (qk >= BASE)
                qk = BASE - 1;

            dq[m] = XP_product(m, dq, y, qk);
            for (int i = m; i > 0; i--) {
                if (rem[i+k] != dq[i])
                    break;
                if (rem[i+k] < dq[i])
                    dq[m] = XP_product(m, dq, y, --qk);
            }

            q[k] = qk; // The k digit of quotient

            // Calculate remainder
            // rem - dq*BASE
            int borrow;
            assert(k >= 0 && k <= m+k);
            borrow = XP_sub(m+1, &rem[k], &rem[k], dq, 0);
            assert(borrow == 0);
        }

        memcpy(r, rem, m);
        for (int i = n-m+1; i < nx; i++)
            q[i] = 0;
        for (int i = m; i < my; i++)
            r[i] = 0;
    }
    return 1;
}

int XP_quotient(int n, T z, T x, int y)
{
    // R = carry * b + x[i]
    // q[i] = R / y
    // carry = R mod y

    int carry = 0;
    for (int i = n-1; i >= 0; i--) {
        carry = carry * BASE + x[i];
        z[i] = carry / y;
        carry %= y;
    }
    return carry; // remainder
}

void XP_lshift(int n, T z, int m, T x, int s, int fill)
{
    fill = fill ? 0xFF : 0;
    // Shift left by s/8 bytes
    int i, j = n-1;
    if (n >= m + s/8)
        //     ------+++ m
        //     |    |
        // ============= n
        i = m - 1;
    else
        // ------+++ m
        //   |  |
        //   ======= n < m + s/8
        //      |
        //      ==== n < m
        i = n - s/8 - 1;
    for (; j >= m + s/8; j--)
        z[j] = 0;
    for (; i >= 0; i--, j--)
        z[j] = x[i];
    for (; j >= 0; j--)
        z[j] = fill;
    // Shift left by s bits
    s %= 8;
    if (s > 0) {
        XP_product(n, z, z, 1 << s); // 1 << s is 2^s
        z[0] |= fill >> (8-s);
    }
}

void XP_rshift(int n, T z, int m, T x, int s, int fill)
{
    fill = fill ? 0xFF : 0;
    // Shift right by s/8 bytes
    //  m +++--------
    //       |   |
    //  n ========
    int i, j = 0;
    for (i = s/8; i < m && j < n; i++, j++)
        z[j] = x[i];
    for (; j < n; j++)
        z[j] = fill;
    // Shift left by s bits
    s %= 8;
    if (s > 0) {
        XP_quotient(n, z, z, 1 << s);
        z[n-1] |= fill << (8 - s);
    }
}

static char map[] = {
	0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
	36, 36, 36, 36, 36, 36, 36,
	10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
	23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35,
	36, 36, 36, 36, 36, 36,
	10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
	23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35
};

int XP_fromstr(int n, T z, const char *str, int base, char **end)
{
    assert(str);
    assert(base >= 2 && base <= 36);

    const char *p = str;
    // Skip white space
    while (*p && isspace(*p))
        p++;

    if (*p && isalnum(*p) && map[*p-'0'] < base) {
        int carry = 0;
        for (; *p && isalnum(*p) && map[*p-'0'] < base; p++) {
            carry = XP_product(n, z, z, base);
            if (carry)
                break;
            XP_sum(n, z, z, map[*p-'0']);
        }
        if (end)
            *end = (char*)p;
        return carry;

    } else {
        if (end)
            *end = (char*)str;
        return 0;
    }
}

char* XP_tostr(char *str, int size, int base, int n, T x)
{
    assert(str);
    assert(base >= 2 && base <= 36);

    int i = 0;
    do {
        int r = XP_quotient(n, x, x, base);
        assert(i < size);
        str[i++] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[r];
        while (n > 1 && x[n-1] == 0)
            n--;
    } while (n > 1 || x[0] != 0);
    assert(i < size);
    str[i] = '\0';

    // Reverse str
    for (int j = 0; j < --i; j++) {
        unsigned char c = str[j];
        str[j] = str[i];
        str[i] = c;
    }
    return str;
}

